home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / btsys.arc / BTISRT.C < prev    next >
Text File  |  1984-12-14  |  5KB  |  195 lines
  1. /*    btisrt        */
  2. #include <stdio.h>
  3. #include <btextern.h>
  4.  
  5. int btisrt (filhand, key, datapt)
  6. int filhand, datapt;
  7. char key[];
  8.  
  9. /*    main routine to insert key into btree    */
  10. {
  11.     int i,j,k,node,holdptr,*ip,klength,occurs;
  12.     char *cp,leaf;
  13.  
  14.     int *new,*temp,last;
  15.  
  16. /* find place to insert the key        */
  17. if ((i = btplace (filhand, key)))
  18.     BTSETCOD (filhand, NULL, 60);    /* set logic error */
  19.  
  20. /* this value is already stored in the stack by btplace */
  21. klength = btfilar[filhand].keylen;
  22. occurs = (LBLEN - 1) / (btfilar[filhand].keylen + 3);
  23. j = pop ();
  24. node = pop ();
  25. leaf = 'Y';
  26.  
  27. again:
  28.  
  29. ip = btfilar[filhand].filbuf + (occurs - 1);
  30. holdptr = *ip;
  31.  
  32. /* set up pointers to move keys over by one position */
  33. ip2 = btfilar[filhand].filbuf + (occurs - 1);    /* start of move */
  34. ip1 = ip2 - 1;    /* from where to move */
  35. ip3 = btfilar[filhand].filbuf + j;    /* till when to move */
  36. while (ip1 >= ip3)    {
  37.     *ip2-- = *ip1--;
  38. }
  39. /* now move keys */
  40. cp2 = (char *)(btfilar[filhand].filbuf + occurs);
  41. cp2 += (occurs - 1)*(klength + 1);    /* where to move */
  42. cp1 = cp2 - (klength + 1);
  43. cp3 = (char *)(btfilar[filhand].filbuf + occurs);
  44. cp3 += j*(klength + 1);
  45.  
  46. while (cp1 >= cp3)    {
  47.     strcpy (cp2,cp1);
  48.     cp1 -= (klength + 1);
  49.     cp2 -= (klength + 1);
  50. }
  51.  
  52. strcpy (cp2,key);
  53. *ip2 = datapt;        /* insert new key and pointer */
  54.  
  55. cp = (char *)btfilar[filhand].filbuf;
  56. cp += (LBLEN - 1);
  57. *cp = leaf;
  58.  
  59. cp = (char *)(btfilar[filhand].filbuf + occurs);
  60. cp += (occurs - 1)*(klength + 1);
  61.  
  62. if ((i = strcmp (cp, "")) == 0)    {
  63.     if ((i = btwrit (filhand, node)))
  64.         BTSETCOD (filhand, node, i);  /* set write error */
  65.     return (0);
  66. }                  
  67.  
  68.     /*    btdivd        */
  69. /* divides a node gets space and writes it out    */
  70.                               
  71. else            {
  72.  
  73. if (!( new = (int*)calloc (LBLEN, (sizeof (char)))))
  74.     BTSETCOD (NULL, NULL, 7);    /* no core */
  75.  
  76. if (!(temp = (int*)calloc (LBLEN, sizeof (char))))
  77.     BTSETCOD (NULL, NULL, 7);    /* no core */
  78.                                       
  79. last = occurs / 2;
  80. k = 0;
  81.  
  82. cp1 = btfilar[filhand].ikeyptr;
  83. cp1 += last*(klength + 1);    /* start of key move */
  84. cp3 = btfilar[filhand].ikeyptr + occurs*(klength + 1);
  85. cp2 = (char*)(new + occurs);    /* init destination */
  86.  while (cp1 < cp3)
  87.     *cp2++ = *cp1++;    /* move keys */
  88.  
  89. ip1 = btfilar[filhand].filbuf;    /* start of pointer area */
  90. ip3 = ip1 + occurs;        /* end of pointers */
  91. ip1 += last;
  92. ip2 = new;            /* init destination */
  93.  
  94. while (ip1 < ip3)
  95.     *ip2++ = *ip1++;    /* move pointers */
  96.  
  97. *ip2 = holdptr;
  98.  
  99. while (++ip2 < (new + occurs))
  100.     *ip2 = NULL;        /* zero all pointers */
  101. cp3 = (char *)new + LBLEN;    /* end of keys */
  102.  
  103. while (cp2 < cp3)
  104.     *cp2++ = '\0';
  105. /* all keys have now been nulled */
  106.  
  107. /* set true flag    */
  108. *((char *)(new) + (LBLEN -1)) = leaf;    /* keep old flag value */
  109.  
  110. /* move to temporary area */
  111. movmem (btfilar[filhand].filbuf, temp, LBLEN);
  112. movmem (new,btfilar[filhand].filbuf, LBLEN);
  113.  
  114. /* write new node */
  115. if ((i = btwrit (filhand, (k = btgetsp (filhand)))))
  116.     BTSETCOD (filhand, k, i);    /* set error */
  117. movmem (temp, btfilar[filhand].filbuf, LBLEN);
  118. cp1 = btfilar[filhand].ikeyptr;
  119. cp1 += (last - 1)*(klength + 1);    /* init pointers */
  120. strcpy (key, cp1);            /* store key */
  121.  
  122. /* now blank all keys and pointers that were moved */
  123. ip1 = btfilar[filhand].filbuf;
  124. ip3 = ip1 + occurs;
  125. ip1 += last;
  126.  
  127. while (ip1 < ip3)
  128.     *ip1++ = NULL;            /* zero all pointers */
  129.  
  130. cp1 = btfilar[filhand].ikeyptr;
  131. cp1 += last*(klength + 1);
  132. cp3 = btfilar[filhand].ikeyptr + occurs*(klength + 1);
  133.  
  134. while (cp1 < cp3)
  135.     *cp1++ = '\0';            /* null all keys */
  136.  
  137. /* now write out changed node */
  138. if ((i = btwrit (filhand, node)))
  139.     BTSETCOD (filhand, node, i);    /* set write error */
  140.  
  141. /* free buffers */
  142. free (temp);
  143. free (new);
  144.  
  145. }    /* end if        */
  146.  
  147. /* check if root node has been split */
  148. datapt = node;          /* save node value before popping stack */
  149. j = pop ();
  150. if ((node = pop ()) != NULL)    {
  151.     if ((i = btread (filhand, node)))
  152.         BTSETCOD (filhand, node,i);
  153.     ip = btfilar[filhand].filbuf + j;
  154.     *ip = k;
  155.     cp = (char *)btfilar[filhand].filbuf;
  156.     cp += (LBLEN - 1);
  157.     leaf = 'N';
  158.     goto again;
  159. }
  160.  
  161. else    {
  162.     ip = btfilar[filhand].filbuf;
  163.     *ip++ = datapt;
  164.     *ip = k;        /* value of new node in root */
  165.  
  166.     cp = btfilar[filhand].ikeyptr;
  167.     strcpy (cp, key);
  168.     cp += (klength + 1);
  169.     strcpy (cp,'\0');
  170.  
  171. /* now clear out rest of new root */
  172.     ip1 = btfilar[filhand].filbuf + 2;     /* starting place */
  173.     ip3 = btfilar[filhand].filbuf + occurs;    /* ending place */
  174.     while (ip1 < ip3)
  175.         *ip1++ = NULL;        /* null it baby ! */
  176.     cp1 = (char *)(btfilar[filhand].filbuf + occurs);
  177.     cp3 = cp1 + occurs*(klength + 1); /* end here */
  178.     cp1 += (klength + 1);
  179.     while (cp1 < cp3)
  180.         *cp1++ = '\0';        /* null keys */
  181.  
  182.     *((char *)(btfilar[filhand].filbuf) + (LBLEN -1)) = 'N';
  183.  
  184. /* write out new root    */
  185.     k = btgetsp (filhand);    /* get a new node for new root */
  186.     if ((i = btwrit (filhand, k)))
  187.         BTSETCOD (filhand, k, i);    /* set error code */
  188.  
  189. /* put new root value in control block */
  190.     btfilar[filhand].root = k;
  191. }    /* end if */
  192.  
  193. return (0);
  194. }    /* end btisrt */
  195.